// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
)

func sortColors(array []int) []int {
	for gap := len(array) / 2; gap > 0; gap = gap / 2 {
		for j := gap; j < len(array); j++ {
			for i := j - gap; i >= 0; i = i - gap {
				if array[i+gap] > array[i] {
					break
				} else {
					array[i+gap], array[i] = array[i], array[i+gap]
				}
			}
		}
	}
	return array
}

func main() {
	array := []int{3, 1, 3, 2, 2, 1}
	res := sortColors(array)
	fmt.Println(res)
}

//$ go run interview6-5.go
//[1 1 2 2 3 3]
